package MonotonicStack;

import java.util.Stack;

/**
 * 原始问题：给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。
 * eg:
 * 给你一个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。
 *
 * 解释：第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4;
 * 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。
 */
public class NextGreaterNumber {
    public static void main(String[] args) {
        int[] input = new int[] {2,1,2,4,3};
        int[] result = new NextGreaterNumber().NextGreaterNumber(input);
        int[] resultI = new NextGreaterNumber().NextGreaterNumberI(input);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }

    public int[] NextGreaterNumber(int[] input) {
        if (input == null || input.length == 0) {
            return null;
        }
        int[] result = new int[input.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = input.length - 1; i >= 0; i--) {
            // 1. 首先判断前面的数字是否大于后面的数字，若大于，则说明后面的数字都被挡住了，无需再关注
            while (!stack.isEmpty() && stack.peek() <= input[i]) {
                stack.pop();
            }
            // 2. 若栈仍不为空，说明栈顶元素大于当前元素，result[i]即为栈顶元素，否则返回-1
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            // 3. 将当前元素放入栈中
            stack.push(input[i]);
        }
        // 4. 返回结果
        return result;
    }

    // 若输入数组为环形数组，将input重复一次即可
    public int[] NextGreaterNumberI(int[] input) {
        if (input == null || input.length == 0) {
            return null;
        }
        int[] result = new int[input.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 2 * input.length - 1; i >= 0; i--) {
            // 1. 首先判断前面的数字是否大于后面的数字，若大于，则说明后面的数字都被挡住了，无需再关注
            while (!stack.isEmpty() && stack.peek() <= input[i % input.length]) {
                stack.pop();
            }
            // 2. 若栈仍不为空，说明栈顶元素大于当前元素，result[i]即为栈顶元素，否则返回-1
            result[i % input.length] = stack.isEmpty() ? -1 : stack.peek();
            // 3. 将当前元素放入栈中
            stack.push(input[i % input.length]);
        }
        // 4. 返回结果
        return result;
    }
}
